How would you compute x raised to the nth power? (for integer n)

	int power (int x, int n) {
	    int result = 1;
	    for (int i = 0; i < n; i++)
	        result *= x;
	    return result;
	}


How would you recursively compute x raised to the nth power?
Perhaps you could compute the power like this?

	int power (int x, int n) {
	    return  x * power (x, n-1);
	}


DEMO	(Power1.java, recursive power without base case)


What's wrong with this method?

	int power (int x, int n) {
	    return  x * power (x, n-1);
	}

	infinite recursion (like infinite loop)


How do you make it stop? Where should it stop?
What's the smallest integer power you can compute this way?

	a number raised to the power 0 is 1

	int power (int x, int n) {
	    if (n == 0)
	        return  1;
	    else
	        return  x * power (x, n-1);
	}


DEMO	(Power1.java, add a base case)


What's a Base Case?

	instance that can be solved without recursion


What's the first Rule of Recursion?

	1. must have a base case



What happens when you call power(2,2)?



What happens when you run the code with a negative power?

	int power (int x, int n) {
	    if (n == 0)
	        return  1;
	    else
	        return  x * power (x, n-1);
	}


DEMO	(Power1.java, give a negative value for n)


What's the second Rule of Recursion?

	2. recursive calls must progress toward base



How can you feel confident that a recursive method works correctly?

	show that if the recursive call gives correct result
	then the remaining computation is correct


Explain why the recursive power method works.


What's the third Rule of Recursion?

	3. assume the recursive call works



What happens when you run the code with a large power (1^100000)?

	stack overflow


DEMO	(stack overflow)



Power can be implemented using recursion or using a loop (iteration).
Which is the better way to write power (recursion or iteration)?
How do you choose between using recursion or iteration?
Does recursion really help or does it just make things more confusing?

	each recursive call has some overhead
	the number of nested recursive calls is limited by stack size
	iteration better for power problem
	recursion gives simpler solution to some problems